package leetcode.stack;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

/**
 * DESCRIPTION: https://leetcode-cn.com/problems/valid-parentheses/
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * Author: ammar
 * Date:   2021/12/15
 * Time:   上午8:56
 */
public class _20_有效的括号 {
    public static void main(String[] args) {
        String s = "()";
        System.out.println(isValid2(s));
        String s1 = "()[]{}";
        System.out.println(isValid2(s1));
        String s2 = "(]";
        System.out.println(isValid2(s2));
        String s3 = "{[]}";
        System.out.println(isValid2(s3));
        String s4 = "{[}}";
        System.out.println(isValid2(s4));
        String s5 = "[";
        System.out.println(isValid2(s5));
        String s6 = "]";
        System.out.println(isValid2(s6));
    }

    private static Map<String, String> couple = new HashMap<>();
    private static List<String> listR = Arrays.asList(new String[]{"}", "]", ")"});
    private static List<String> listL = Arrays.asList(new String[]{"{", "[", "("});


    static {
        couple.put("{", "}");
        couple.put("(", ")");
        couple.put("[", "]");
    }

    /**
     * 思路：将第一个括号入栈，然后遇到左括号入栈
     * 遇到右括号出栈，并比较
     *
     * @param s
     * @return
     */
    public static boolean isValid1(String s) {
        Stack<Character> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            if (couple.get(String.valueOf(aChar)) != null) stack.push(aChar);
            else {
                if (listR.indexOf(String.valueOf(aChar)) != -1) {
                    if (stack.isEmpty()) return false;
                    Character peek = stack.peek();
                    if (couple.get(String.valueOf(peek)).equals(String.valueOf(aChar))) {
                        stack.pop();
                    } else return false;
                }
            }
        }
        return stack.isEmpty();
    }

    /**
     * 思路：将第一个括号入栈，然后遇到左括号入栈
     * 遇到右括号出栈，并比较
     *
     * @param s
     * @return
     */
    public static boolean isValid2(String s) {
        Stack<String> stack = new Stack<>();
        char[] chars = s.toCharArray();
        for (char aChar : chars) {
            String str = String.valueOf(aChar);
            if (listL.indexOf(str) != -1) {
                stack.push(str);
                continue;
            }
            if (listR.indexOf(str) != -1) {
                if (stack.isEmpty()) return false;
                if (!couple.get(stack.pop()).equals(str)) return false;
            }
        }
        return stack.isEmpty();
    }

    /**
     * 字符串操作效率太低了！！！！！！！！
     * @param s
     * @return
     */
    public static boolean isValid3(String s) {
        while (s.contains("{}") || s.contains("[]") || s.contains("()")) {
            s = s.replace("{}", "");
            s = s.replace("[]", "");
            s = s.replace("()", "");
        }
        return s.isEmpty();
    }
}
